"""
插入排序
分为 有序区 和 无序区
默认 有序区 为列表第一个元素
从无序区中，依次跟有序区的元素比较，决定插入位置

时间复杂度O(n的平方)
"""


def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]  # 当前摸到的数
        j = i - 1  # 有序区的最大下标
        while j >= 0 and li[j] > tmp:
            li[j + 1] = li[j]  # 挪位
            j -= 1  # 有序区的下一个数
        li[j + 1] = tmp
        print(li)


if __name__ == '__main__':
    li = [5, 4, 3, 2, 1, 0]
    print(li)
    insert_sort(li)
